﻿// 1008train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <bitset>

using namespace std;

/*
 对一个给定的值b取模。如果得到的结果小于一个给定的值c，
 则数据a为有效类型，其类型为取模的值
 比如一个数据a = 0x01010101，b=3，按照分类方法计算
 （0x01+0x01+0x01+0x01）% 3 = 1
 所以如果c=2，则此a为有效类型，其类型为1，如果c=1，则此a为无效类型

输入描述
输入12个数据，用空格分隔，第一个数据为c，第二个数据为b，剩余10个数据为需要分类的数据

输出描述
输出最多数据的有效类型有多少个数据

输入
3 4 256 257 258 259 260 261 262 263 264 265
输出
3

对4取模的结果为1 2 3 0 1 2 3 0 1 2，c为3，所以0 1 2都是有效类型，
类型为1和2的有3个数据，类型为0的只有2个数据，故输出3
 */
class Solution01
{
public:
    int getRemain(int num)
    {
        int length = 8;

        string binary_str = bitset<32>(num).to_string();

        string hex_str;
        //32位整数，4位截出来，转成十进制，再转成16
        for (int i=0; i<32; i+=8)
        {
            string curr = binary_str.substr(i, 8);
            bitset<32>bs(curr);
            uint32_t num = bs.to_ulong();
            stringstream hex_sstream;
            hex_sstream << hex << num;
            string curr_hex = hex_sstream.str();
            while (curr_hex.size() < 2)
            {
                curr_hex = '0' + curr_hex;
            }
            hex_str += curr_hex;
        }

        //10个数据4个字节相加后的结果分别为1 2 3 4 5 6 7 8 9 10
        int sum = 0;
        for (int i=0; i<length; i+=2)
        {
            stringstream item_sstream;
            item_sstream << hex_str[i] << hex_str[i + 1];
            string item = item_sstream.str();
            sum += stoi(item, nullptr, 16);
        }
        return sum % split_;
	    //
    }

    void solve(int split, int limit, vector<int>& num_vec)
    {
        split_ = split;
        for (auto& num : num_vec)
        {
            int kind = getRemain(num);
            //小于c，则数据a为有效类型
            if (kind < limit)
            {
                kind_map[kind].push_back(num);
            }
        }

        int result = 0;
        for (auto& map_item : kind_map)
        {
            int size = map_item.second.size();
            result = max(size, result);
        }
        cout << result;
    }

    Solution01(int split, int limit, vector<int>& num_vec)
    {
        solve(split, limit, num_vec);
	    //
    }
private:
    int split_ = 0;
    unordered_map<int, vector<int>>kind_map;
    //
};


class Solution11
{
public:
    int getRemain(uint32_t num)
    {
        uint32_t res1 = (num >> 24) & 0xFF;
        uint32_t res2 = (num >> 16) & 0xFF;
        uint32_t res3 = (num >> 8) & 0xFF;
        uint32_t res4 = num & 0xFF;

        int sum = res1 + res2 + res3 + res4;
        return sum % split_;
    }

    Solution11(int split, int limit, vector<uint32_t>& num_vec)
    {
        split_ = split;
        int v_size = num_vec.size();

        for (int i=0; i<v_size; i++)
        {
            uint32_t curr = num_vec[i];
            int kind = getRemain(curr);
            if (kind<limit)
            {
                kind_map[kind].push_back(curr);
            }
	        //
        }

        int result = 0;
        for (auto&map_item:kind_map)
        {
            int size = map_item.second.size();

            result = max(size, result);
        }
        cout << result;
	    //
    }
private:
    int split_ = 0;
    unordered_map<int, vector<uint32_t>>kind_map;
};


/*
有一辆汽车需要从 m*n 的地图的左上角(起点)开往地图的右下角(终点)，
去往每一个地区都需要消耗一定的油量，加油站可进行加油

请你计算汽车确保从起点到达终点时所需的最少初始油量说明:
(1) 智能汽车可以上下左右四个方向移动1
(2) 地图上的数字取值是 0或-1 或者正整数:
-1: 表示加油站，可以加满油，汽车的油箱容量最大为 100;
0: 表示这个地区是障碍物，汽车不能通过
正整数: 表示汽车走过这个地区的耗油量
(3) 如果汽车无论如何都无法到达终点，则返回 -1


输入描述
第一行为两个数字，M，V，表示地图的大小为 M,N(0< M,N < 200)

后面一个M*N 的矩阵，其中的值是 0 或 -1 或正整数，加油站的总数不超过 200个
输出描述
如果汽车无论如何都无法到达终点，则返回-1
如果汽车可以到达终点，则返回最少的初始油量


示例1
输入
2,2
10,20
30,40
输出
70

示例2
输入
4,4
10,30,30,20
30,30,-1,10
0,20,20,40
10,-1,30,40
输出
70

示例3
输入

4,5
10,0,30,-1,10
30,0,20,0,20
10,0,10,0,30
10,-1,30,0,10
输出
60

示例4
输入
4,4
10,30,30,20
30,30,20,10
10,20,10,40
10,20,30,40
输出
-1
 */
class Solution02
{
public:
    struct Node
    {
        int row, col, val;
        Node() = default;
        Node(int row, int col, int val) :row(row), col(col), val(val) {};
    };
    
    bool bfs(deque<Node>&bfs_queue, vector<vector<int>>& grid)
    {
        while (!bfs_queue.empty())
        {
            Node top_node = bfs_queue.front();
            bfs_queue.pop_front();

            for (auto&dir_v:DirectionGrid)
            {
                int row = top_node.row + dir_v[0];
                int col = top_node.col + dir_v[1];

                bool is_row = row >= 0 && row < row_size_;
                bool is_col = col >= 0 && col < col_size_;

                if (!is_row || !is_col) continue;

                //0 表示障碍物
                if (grid[row][col] == 0) continue;
                
                if (top_node.val < grid[row][col]) continue;

                int new_val = 0;
                if (grid[row][col]==-1)
                {
                    new_val = 100;
                }
                else
                {
                    new_val = top_node.val - grid[row][col];
                }
                if (new_val > oil_grid[row][col])
                {
                    oil_grid[row][col] = new_val;
                    bfs_queue.push_back(Node(row, col, new_val));
                }

	            //
            }

        	//
        }

        return oil_grid[row_size_ - 1][col_size_ - 1]!=-1;
	    //
    }
    Solution02(vector<vector<int>>&grid, int row_size, int col_size)
    {
        row_size_ = row_size;
        col_size_ = col_size;

        int left = 0, right = 101;
        int result = -1;
        while (left<right)
        {
            int mid = left + (right - left) / 2;
            oil_grid = vector<vector<int>>(row_size_, vector<int>(col_size_, -1));
            deque<Node>bfs_queue;
            int start_val = mid - grid[0][0];
            bfs_queue.push_back(Node(0, 0, start_val));
            oil_grid[0][0] = mid;

            if (bfs(bfs_queue,grid))
            {
	            //缩小油量
                result = mid;
                right = mid;
            }
            else
            {
	            //加大油量
                left = mid + 1;
            }

	        //
        }
        cout << result;
	    //
    }
    //
private:
    int row_size_ = 0, col_size_ = 0;
    vector<vector<int>>oil_grid;
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
};


vector<int>handleStr(string&split_str)
{
    vector<int>num_vec;
    stringstream split_sstream(split_str);
    string token;
    while (getline(split_sstream,token,','))
    {
        num_vec.push_back(stoi(token));
    }
    return num_vec;
	//
}

int main()
{
	{
/*
4,4
10,30,30,20
30,30,20,10
10,20,10,40
10,20,30,40
*/
        string size_str;
        getline(cin, size_str);
        vector<int>size_v = handleStr(size_str);
        int row_size = size_v[0], col_size = size_v[1];
        vector<vector<int>>grid(row_size);
        for (int i=0; i<row_size; i++)
        {
            string row_str;
            getline(cin, row_str);
            vector<int>item = handleStr(row_str);
            grid[i] = item;
        }
        Solution02 solu(grid, row_size, col_size);

        return 0;
	}
    //第一个数据为c，第二个数据为b
    int limit, split;
    cin >> limit >> split;
    //剩余10个数据
    vector<uint32_t>num_vec(10);
    for (int i=0; i<10; i++)
    {
        cin >> num_vec[i];
    }
    Solution11 solu(split, limit, num_vec);
    //Solution01 solu;

    //cout << solu.getRemain(305419896);
	//换成十六进制是：0x12345678
    return 0;
    //
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
